import java.nio.charset.StandardCharsets;
import java.util.*;

public class project {
    public List<List<String>> partition(String s) {
        List<List<String>> list=new ArrayList<>();
        Deque<String> deque=new ArrayDeque<>();
        int len=s.length();
        if(len==0){
            return list;
        }
        char[] chars=s.toCharArray();
        dfs(0,len,chars,deque,list);
        return list;
    }
    public void dfs(int start,int end,char[] chars,Deque<String> deque,List<List<String>> list){
        if(start==end){
            list.add(new ArrayList<>(deque));
            return;
        }
        for(int i=start;i<end;i++){
            if(!inspect(chars,start,i)){
                continue;
            }
            deque.addLast(new String(chars,start,i-start+1));
            dfs(i+1,end,chars,deque,list);
            deque.removeLast();
        }
    }
    public boolean inspect(char[] chars,int left,int right){
        while (left<right){
            if(chars[left]!=chars[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

























    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> list=new ArrayList<>();
        int len=nums.length;
        for(int i=0;i<l.length;i++){
            int left=l[i];
            int right=r[i];
            int[] arr=new int[right-left+1];
            for(int j=left;j<=right;j++){
                arr[j-left]=nums[j];
            }
            Arrays.sort(arr);
            if(arr.length<2){
                list.add(true);
                continue;
            }
            int tmp=arr[1]-arr[0];
            boolean bool=true;
            for(int j=2;j<arr.length;j++){
                if(tmp!=arr[j]-arr[j-1]){
                    bool=false;
                    list.add(bool);
                    break;
                }
            }
            if(bool){
                list.add(bool);
            }
        }
        return list;
    }






















    public List<String> generateParenthesis(int n) {
        List<String> list=new ArrayList<>();
        char[] str=new char[n*2];
        dfs1(0,str,list);
        return list;
    }
    public void dfs1(int start,char[] str,List<String> list){
        if(str.length==start){
            if(inspect1(str)){
                list.add(new String(str));
            }
        }else{
            str[start] = '(';
            dfs1(start + 1, str, list);
            str[start] = ')';
            dfs1(start + 1, str, list);
        }
    }
    public boolean inspect1(char[] str){
        int count=0;
        for(char ch : str){
            if(ch=='('){
                count++;
            }else{
                count--;
            }
            if(count<0){
                return false;
            }
        }
        return count==0;
    }














    public int[] deckRevealedIncreasing(int[] deck) {
        int len=deck.length;
        Arrays.sort(deck);
        Queue<Integer> queue=new ArrayDeque<>();
        for(int i=len-1;i>=0;i--){
            queue.add(deck[i]);
            if(i==0){
                break;
            }
            queue.add(queue.poll());
        }
        for(int i=len-1;i>=0;i--){
            deck[i]=queue.poll();
        }
        return deck;
    }














    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int count=0;
        int len=piles.length;
        int average=len/3;
        int index=len-2;
        for(int i=0;i<average;i++){
            count+=piles[index];
            index-=2;
        }
        return count;
    }




















    public boolean canBeValid(String s, String locked) {
        int len = s.length();
        if(s==null||len%2==1){
            return false;
        }
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2=new Stack<>();
        for(int i=0;i<len;i++){
            char ch=locked.charAt(i);
            char c=s.charAt(i);
            if(ch=='1'){
                if(c=='('){
                    stack2.push(i);
                }else{
                    if(!stack2.isEmpty()){
                        stack2.pop();
                    }else if(!stack1.isEmpty()){
                        stack1.pop();
                    }else{
                        return false;
                    }
                }
            }else{
                stack1.push(i);
            }
        }
        while (!stack1.isEmpty()&&!stack2.isEmpty()){
            if(stack1.pop()<stack2.pop()){
                return false;
            }
        }
        return stack1.size()%2==0&&stack2.isEmpty();
    }




















    public int[][] construct2DArray(int[] original, int m, int n) {
        if(m*n<original.length||m*n>original.length){
            return new int[][]{};
        }
        int[][] arr=new int[m][n];
        int k=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(k<original.length){
                    arr[i][j]=original[k++];
                }else{
                    break;
                }
            }
        }
        return arr;
    }


















    public int[] maxDepthAfterSplit(String seq) {
        int len=seq.length();
        int[] arr=new int[len];
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<len;i++){
            char ch=seq.charAt(i);
            if(ch=='('){
                stack.push(i);
            }else{
                int size=stack.size();
                int tmp=stack.pop();
                if(size%2==0){
                    arr[i]=1;
                    arr[tmp]=1;
                }else{
                    continue;
                }
            }
        }
        return arr;
    }
}
